package test;

/**
 * Min Heap
 */
public class MinHeap {

    static int[] as = new int[]{53, 17, 78, 9, 45, 65, 87, 23, 2};
    static int length = 0;

    public static void main(String[] args) {
        length = as.length;
        //create
        createHeap1();
        printAll();

        //insert
        //insert(2);
        //printAll();

        //delete one
        delete(1);
        printAll();
    }

    private static void delete(int index) {
        as[index] = as[length - 1];
        shiftDown(index);

        as[length - 1] = -1;
    }

    private static void printAll() {
        System.out.println("new array is:");
        for (int i : as) {
            System.out.print(i + ",");
        }
        System.out.println("");
    }

    private static void createHeap1() {
        for (int i = length / 2; i >= 0; i--) {
            shiftDown(i);
        }
    }

    private static void shiftDown(int i) {
        int k = i;

        //left
        if ((2 * i + 1) < length) {
            if (as[2 * i + 1] < as[i])
                k = 2 * i + 1;
        }

        //right
        if ((2 * i + 2) < length) {
            if (as[2 * i + 2] < as[i])
                k = 2 * i + 2;

            if (as[2 * i + 1] < as[k])
                k = 2 * i + 1;
        }

        if (k != i) {
            swap(k, i);

            shiftDown(k);
        }
    }

    static void shiftUp(int[] array, int index) {
        int parent = (index - 1) / 2;
        if (parent < 0)
            return;

        if (array[parent] > array[index]) {
            int tmp = array[parent];
            array[parent] = array[index];
            array[index] = tmp;

            shiftUp(array, parent);
        }
    }

    static void insert(int value) {
        int[] tas = new int[length + 1];
        for (int i = 0; i < as.length; i++) {
            tas[i] = as[i];
        }
        tas[length] = value;
        length++;

        shiftUp(tas, length - 1);
        as = tas;
    }

    private static void swap(int k, int i) {
        int tmp = as[k];
        as[k] = as[i];
        as[i] = tmp;
    }

}
